package leetcode.greed;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Scanner;
import java.util.stream.Collectors;

/**
 * leetCode 300
 * 最长递增子序列
 * 给定两个单词 word1 和 word2，计算出将 word1 转换成 word2 所使用的最少操作数
 * 思路：贪心
 * 进阶： 贪心算法

 */
public class Greed300 {

    public static void main(String []args){
        Scanner sc = new Scanner(System.in);
        //利用hasNextXXX()判断是否还有下一输入项
        while (sc.hasNext()) {
            //利用nextXXX()方法输出内容
            String str = sc.next();
            List<Integer> input = Arrays.stream(str.split(",")).map(i -> { return Integer.parseInt(i); }).collect(Collectors.toList());
            System.out.println(Arrays.toString(input.toArray()));
            Integer [] nums = input.toArray(new Integer[input.size()]);
            new Greed300().lengthOfLIS(nums);
        }
    }
    public int lengthOfLIS(Integer [] nums) {
        if (nums.length == 0 ) return 0;
        List<Integer> res = new ArrayList<>();
        res.add(nums[0]);//3,5,6,2,5,4,19,5,6,7,12
        for(int i = 1; i < nums.length ; i ++){
            if(nums[i] > res.get(res.size() - 1)){
                res.add(nums[i]);
            } else if (nums[i] < res.get(res.size() - 1)){
                int replace = find(res, nums[i]);
                res.set(replace, nums[i]);
            }
        }
        return res.size();
    }

    public int find(List<Integer> res, int k){
        int l = 0,  r = res.size();
        while (l < r) {
            int mid = l + (r - l) / 2;
            // 有就啥都不做了
            if (k == res.get(mid)) {
                l = mid;
                return l;
            } else if (k <= res.get(mid)) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        return l;
    }
}
